<?php 
/** 
 * 合并两个排序的链表
 */
class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}

/** 
 * 递归
 * [merge description]
 * @param  [type] $pHead1 [description]
 * @param  [type] $pHead2 [description]
 * @return [type]         [description]
 */
function merge($pHead1, $pHead2) 
{
	if ($pHead1 == null) {
		return $pHead2;
	}
	if ($pHead2 == null) {
		return $pHead1;
	}
	if ($pHead1->val <= $pHead2->val) {
		$pHead1->next = merge($pHead1->next, $pHead2);
		return $pHead1;
	} else {
		$pHead2->next = merge($pHead1, $pHead2->next);
		return $pHead2;
	}
}


// 非递归
function merge1($pHead1, $pHead2) 
{
	$newNode = null;
	$curNode = null;
	while ($pHead1 != null && $pHead2 != null) {
		if ($pHead1->val <= $pHead2->val) {
			if ($newNode == null) {
				$curNode = $pHead1;
				$newNode = $curNode;
			} else {
				$curNode->next = $pHead1;
				$curNode = $curNode->next;
			}
			$pHead1 = $pHead1->next;
		} else {
			if ($newNode == null) {
				$curNode = $pHead2;
				$newNode = $curNode;
			} else {
				$curNode->next = $pHead2;
				$curNode = $curNode->next;
			}
			$pHead2 = $pHead2->next;
		}
	}

	if ($pHead1 == null) {
		$curNode->next = $pHead2;
	} else {
		$curNode->next = $pHead1;
	}
	return $newNode;
}

$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$head1 = new ListNode(2);
$head1->next = new ListNode(3);
$head1->next->next = new ListNode(5);
$head1->next->next->next = new ListNode(7);
$head1->next->next->next->next = new ListNode(9);


$node = merge1($head, $head1);
while ( !is_null($node) ) {
	echo $node->val.PHP_EOL;
	$node = $node->next;
}

